const { ListNode, LinkedList } = require('../2. 链表/1. 链表基础/1. 建立线性链表.js')
// 给定一个链表的头节点head，删除链表的倒数第n个节点，并返回链表的头节点
// 思路，快慢双指针法
// 该题为删除倒数第n个位置的节点,定义fast和slow两个指针,先让快指针走n次,然后让快慢指针同时走
// 当fast走到头,slow刚好走到倒数第n个的前一位,删除下一位即可

function removeNthFromEnd(head, n) {
    let dummyHead = new ListNode(0, head)
    let fast = head
    let slow = dummyHead // 要找到倒数第n个节点的前一位，所以用虚拟节点开始
    while (n--) {
        fast = fast.next
    }
    
    while (fast) {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return dummyHead.next
}

let list = new LinkedList([2, 5, 1, 7, 3, 9])
let res = removeNthFromEnd(list.head, 2)
console.log(res);